package array

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
)

/*
	动态数组,具有缩容和扩容的能力
	扩容策略: 当元素个数要大于容量的时候,扩容为二倍
	缩容策略: 当元素个数等于容量的1/4的时候进行缩容,缩容为当前容量1/2(1/4缩容为1/2是避免复杂度的震荡)
*/
type DynamicArray struct {
	data []interface{}

	size int
}

func (array DynamicArray) ToSlice() []interface{} {
	if array.size == cap(array.data) {
		return array.data
	} else {
		newSlice := make([]interface{}, array.size, array.size)
		copy(newSlice, array.data)
		return newSlice
	}
}

func (array DynamicArray) String() string {
	res := fmt.Sprintf("DynamicArray: size = %d , capacity = %d ", array.size, cap(array.data))
	res += "["
	for i := 0; i < array.size; i++ {
		res += fmt.Sprintf("%v", array.data[i])
		if i != array.size-1 {
			res += ", "
		}
	}
	res += "]"
	return res
}

func (array *DynamicArray) Iterator(iteratorFunc func(iterator common.Iterator) bool) {
	dynamicArrayIterator := &DynamicArrayIterator{data: array.data}
	var iterator common.Iterator = dynamicArrayIterator
	removeIndexMap := make(map[int]byte)
	for i := 0; i < array.size; i++ {
		dynamicArrayIterator.removeFlag = false
		dynamicArrayIterator.index = i
		stop := iteratorFunc(iterator)
		if dynamicArrayIterator.removeFlag {
			// 增加删除的标记
			removeIndexMap[i] = 0
		}
		if stop {
			break
		}
	}
	array.removeElementByIndexMap(removeIndexMap)
}

func (array DynamicArray) Size() int {
	return array.size
}

func (array DynamicArray) IsEmpty() bool {
	return array.size == 0
}

func (array *DynamicArray) Add(index int, item ...interface{}) {
	// 对index进行处理
	if index < 0 {
		index = 0
	} else if index > array.size {
		index = array.size
	}
	// 进行扩容操作
	capacity := cap(array.data)
	if len(item)+array.size < 0 {
		// 数组大小超过限制
		panic("OUT OF MEMORY")
	}
	for len(item)+array.size > capacity {
		capacity = capacity * 2
		if capacity < 0 {
			// 超过大小限制的时候,分配恰好的内存空间
			capacity = len(item) + array.size
		}
	}
	if capacity > cap(array.data) {
		// 进行扩容
		newData := make([]interface{}, capacity, capacity)
		// 拷贝index之前的元素
		for i := 0; i < index; i++ {
			newData[i] = array.data[i]
		}
		// 将新增元素插入
		for i := index; i < index+len(item); i++ {
			newData[i] = item[i-index]
		}
		// 拷贝剩余的元素
		for i := index + len(item); i < array.size+len(item); i++ {
			newData[i] = array.data[i-len(item)]
		}
		array.data = newData
	} else {
		// 将index和之后的元素后移len(item)
		for i := array.size - 1; i >= index; i-- {
			array.data[i+len(item)] = array.data[i]
		}
		// 插入新的元素
		for i := index; i < index+len(item); i++ {
			array.data[i] = item[i-index]
		}
	}
	// 更新元素个数
	array.size += len(item)
}

func (array *DynamicArray) AddFirst(item ...interface{}) {
	array.Add(0, item...)
}

func (array *DynamicArray) AddLast(item ...interface{}) {
	array.Add(array.size, item...)
}

func (array *DynamicArray) Remove(index int) (interface{}, error) {
	if index < 0 || index > array.size-1 {
		return nil, common.IndexError{}
	}
	retValue := array.data[index]
	if cap(array.data)/4 > array.size-1 && cap(array.data) != 0 {
		// 需要进行缩容
		newCapacity := cap(array.data) / 2
		newData := make([]interface{}, newCapacity, newCapacity)
		for i := 0; i < index; i++ {
			newData[i] = array.data[i]
		}
		for i := index + 1; i < array.size; i++ {
			newData[i-1] = array.data[i]
		}
		array.data = newData
	} else {
		// 直接删除
		for i := index; i < array.size-1; i++ {
			array.data[i] = array.data[i+1]
		}
		// help for gc
		array.data[array.size-1] = nil
	}
	array.size--
	return retValue, nil
}

func (array *DynamicArray) RemoveFirst() (interface{}, error) {
	return array.Remove(0)
}

func (array *DynamicArray) RemoveLast() (interface{}, error) {
	return array.Remove(array.size - 1)
}

func (array *DynamicArray) RemoveElement(value interface{}) {
	index := array.FindFirst(value)
	if index != -1 {
		_, _ = array.Remove(index)
	}
}

func (array *DynamicArray) RemoveIfMatch(matchFunc func(interface{}) bool) int {
	if array.IsEmpty() {
		return 0
	}
	removeIndexMap := make(map[int]byte)
	for i := 0; i < array.size; i++ {
		if matchFunc(array.data[i]) {
			removeIndexMap[i] = 0
		}
	}
	array.removeElementByIndexMap(removeIndexMap)
	return len(removeIndexMap)
}

func (array *DynamicArray) RemoveAllElement(value interface{}) int {
	removeValue := array.RemoveIfMatch(func(item interface{}) bool {
		return value == item
	})
	return removeValue
}

func (array DynamicArray) Set(index int, value interface{}) {
	if index < 0 || index > array.size-1 {
		return
	}
	array.data[index] = value
}

func (array DynamicArray) Get(index int) (interface{}, error) {
	if index < 0 || index > array.size-1 {
		return nil, common.IndexError{}
	}
	return array.data[index], nil
}

func (array DynamicArray) GetFirst() (interface{}, error) {
	return array.Get(0)
}

func (array DynamicArray) GetLast() (interface{}, error) {
	return array.Get(array.size - 1)
}

func (array DynamicArray) Contains(value interface{}) bool {
	for i := 0; i < array.size; i++ {
		if value == array.data[i] {
			return true
		}
	}
	return false
}

func (array DynamicArray) FindFirst(value interface{}) int {
	for i := 0; i < array.size; i++ {
		if value == array.data[i] {
			return i
		}
	}
	return -1
}

func (array DynamicArray) FindLast(value interface{}) int {
	lastIndex := -1
	for i := 0; i < array.size; i++ {
		if value == array.data[i] {
			lastIndex = i
		}
	}
	return lastIndex
}

/*
	根据索引集合删除元素
*/
func (array *DynamicArray) removeElementByIndexMap(removeIndexMap map[int]byte) {
	// 集中删除元素
	if len(removeIndexMap) > 0 {
		j := 0
		for i := 0; i < array.size; i++ {
			if _, contains := removeIndexMap[i]; contains {
				j++
			} else {
				array.data[i-j] = array.data[i]
			}
		}
		// help for gc
		for i := array.size - len(removeIndexMap); i < array.size; i++ {
			array.data[i] = nil
		}
	}
	// 维护元素个数
	array.size -= len(removeIndexMap)
	// 尝试缩容
	array.resize()
}

/*
	进行容量调整
*/
func (array *DynamicArray) resize() {
	// 当前元素个数小于容量的1/4的时候,将容量缩小为1/2
	if cap(array.data)/4 > array.size && cap(array.data)/2 != 0 {
		newCapacity := cap(array.data) / 2
		newData := make([]interface{}, newCapacity, newCapacity)
		for i := 0; i < array.size; i++ {
			newData[i] = array.data[i]
		}
	}
}

/*
	sliceArray迭代器,用于再遍历的过程中删除元素和修改元素
*/
type DynamicArrayIterator struct {
	// 数据
	data []interface{}

	index int

	removeFlag bool
}

/*
	删除节点
*/
func (iterator *DynamicArrayIterator) Remove() {
	if iterator.removeFlag {
		return
	}
	// 标记标识删除了元素
	iterator.removeFlag = true
}

/*
	修改节点的值
*/
func (iterator DynamicArrayIterator) Set(value interface{}) error {
	if iterator.removeFlag {
		return common.OperatorNotUseful{}
	}
	// 修改切片中对应元素的值
	iterator.data[iterator.index] = value
	return nil
}

/*
	获取value
*/
func (iterator DynamicArrayIterator) Get() (interface{}, error) {
	if iterator.removeFlag {
		return nil, common.OperatorNotUseful{}
	}
	return iterator.data[iterator.index], nil
}
